/*
 *  以前的 短匹配是我自己写的，现在知道了compare_strings_by_kmp算法的匹配比我的要好
 *  现在将我的算法进行修改，以 compare_strings_by_kmp 代替
 *      2019-04-30
 * */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define __DEBUG_PRINTF__
    #include "debug.h"
#define GET_MAX_FROM_TWO( a, b) ( (a) > (b)?(a) : (b) )
#define GET_MIN_OF_THREE(a,b,c) ( (a)<(b)?( (a)<(c)?(a):(c) ):( (b)<(c)?((b)):(c) ) )

#define WIDTH 255

#define DIFFERENT -1
#define ALIKE 1
#define TWINS 0

int Levenshtein_Distance(const char str1[WIDTH + 1], const char str2[WIDTH + 1])
{
	// Adapt from: http://t.cn/SUfFkz
	int Matrix[WIDTH + 1][WIDTH + 1];
	int temp = 0;
	char ch1, ch2;
	int i = 0, j = 0;	
	int n ,m;
    if(str1 == NULL) return 0;
    if(str2 == NULL) return 0;
	n = strlen(str1);
	m = strlen(str2);
    if (n == 0)   return m;
    if (m == 0)   return n;

	for (i = 0; i <= n; i++)
	{
		Matrix[i][0] = i;	//初始化第一列
	}

	for (j = 0; j <= m; j++)
	{
		Matrix[0][j] = j;	//初始化第一行
	}

	for (i = 1; i <= n; i++)
	{
		ch1 = str1[i - 1];
	    for (j = 1; j <= m; j++)
	    {
	    	ch2 = str2[j - 1];
	    	temp = (ch1==ch2)?0:1;
			Matrix[i][j] = GET_MIN_OF_THREE(Matrix[i - 1][j] + 1, Matrix[i][j - 1] + 1, Matrix[i - 1][j - 1] + temp);
	    }
	}

	return Matrix[n][m];
}

float LevenshteinDistancePercent(const char str1[WIDTH], const char str2[WIDTH])
{
	/// 计算字符串相似度
	int val = Levenshtein_Distance(str1, str2);
	return 1 - (float)val / GET_MAX_FROM_TWO(strlen(str1), strlen(str2));
}

#ifndef    _compare_strings_by_kmp_H_

#define KMP_MAX_SIZE 100


//得出target中的匹配值
int kmp_get_value(char * target, int *value)
{
    char *head,*tail;
    int temp;
    //ABCDABD
    //ABCDAB
    int i = 1, j = 0;
    head = (char *)malloc(sizeof(char) * KMP_MAX_SIZE);
    tail = (char *)malloc(sizeof(char) * KMP_MAX_SIZE);

    if(!head || !tail)
    {
        return DIFFERENT;
    }

    for(i = 1; i < strlen(target); i++){  //从头到尾

        j = 0;
        while(target[j] != '\0'){  //复制到临时数组
            head[j] = target[j];
            tail[j] = target[j];
            j++;
            head[j]='\0';
            tail[j] = '\0';
        }

        head[i] = '\0';
        tail[i+1] = '\0';

        for(j = 0; j < i ; j++){
            if(strcmp(head,tail+1+j)==0){  //比较
                value[i] = strlen(head);
                break;
            }
            temp = strlen(head) - 1;
            head[temp] = '\0';
        }
    }

    free(head);
    free(tail);
    return TWINS;
}

//compare_strings_by_kmp处理过程
int compare_strings_by_kmp(const char *source,const char *target,const int *value)
{
    int i = 0,j = 0;
    
    while(i < strlen(source))
    {  //不回溯，source走到尾

        if(source[i] == target[j] && j<strlen(target))
        {
            i++, j++;
        }else if(j>=strlen(target))
        {
            //DEBUG("找到...");
            return TWINS;
        }else if(source[i]!=target[j]){
            if(j==0){
                j=0;
                i++;
            }else{
                j =  value[j-1];
            }
        }
    }
    if(i >=strlen(source) && j>=strlen(target))
    {
        return TWINS;//DEBUG("找到...");
    }
    else 
    {
        return DIFFERENT;//DEBUG("未找到...");
    }
    return DIFFERENT;
}

#endif /* _compare_strings_by_kmp_H_ */


/*
 * compare_strings_by_LevenshteninDistance
 *
 * 返回值： 
 *      > 0.75 -> 0 -> 相似度很高0
 *      0.50 ~ 0.75 -> 一般相似度1
 *      <0.50       -> 不匹配-1
 * */
int compare_strings_by_LevenshteninDistance(const char str1[WIDTH + 1], const char str2[WIDTH + 1])
{
	float LDrtval;

    LDrtval = LevenshteinDistancePercent(str1,str2);
    if(LDrtval >= 0.50)
    {
        if(LDrtval > 0.75)  {  return TWINS;  }
        else                {  return ALIKE;  }
    }else
    {   return DIFFERENT;   }
}

#if 1
// for demo
int main(void)
{
    //source源字符串，target要匹配的字符串
    char source[KMP_MAX_SIZE] = {"helloworld"};
    char target[KMP_MAX_SIZE] = {"helloworld"}; 
    int value[KMP_MAX_SIZE]={0};  //存放compare_strings_by_kmp匹配值
    int ret;

    // Levenshtein_Distance
	ret = compare_strings_by_LevenshteninDistance(source, target);
    printf("[ LSD ]ret = %d\n", ret);
    printf("返回值： 相似度很高0 一般相似度1 不匹配-1\n");

    printf("\n\n");

    // KMP
    //kmp_init(&source,&target,&value);  //初始化字符串(原有的版本是使用二级指针实现的，最后没有释放内存)
    kmp_get_value(target,value);
    ret = compare_strings_by_kmp(source,target,value);
    printf("[ KMP ]ret = %d\n", ret);
    printf("返回值： 相似度很高0  不匹配-1\n");
    //kmp_free(&source,&target,&value);
    return 0;
}

#endif




#if 0
int str_short_match(const char item[WIDTH],const char source[WIDTH])
{
#define SEARCH_THRESHOLD 2
/*	
 *	我自己写的匹配算法，但不够灵活
	Assume: #SEARCH_THRESHOLD  = 2; (customizable)
		搜索容错度,由于算法采用不完全匹配搜索,当超过 #SEARCH_THRESHOLD#个 不匹配时,停止搜索并反馈现有结果.
		搜索实现了: 从item匹配到的source第一个首字开始以后的其他字符判断剩余位置,直到尾部或DIFFERENTcounter大于SEARCH_THRESHOLD
	返回值:
		0	:	匹配度很高
		1	:	匹配度一般
		-1	:	不匹配
*/
	int DIFFERENTcounter = 0; 	//  if #DIFFERENTcounter is not smaller than #SEARCH_WEIGHT#, stop search and list the result.
	int i, n, counter;		//	for the cycle.

	if((source == NULL) || (item == NULL))
	{
			return -1;
	}else
	{
		if((strcmp(source, "") == 0) || (strcmp(item, "") == 0))
  		{
        	return -1;
    	}else
    	{
    		if(strlen(item) > strlen(source))
    		{
    			return -1;
    		}
    	}
	}

	// Locate the head-char of #item from #source, it will be in vain without the head-char location.
	// Note: #counter is regarded as the '#flag in here.
	for(i = 0,n = 0,counter = 0;source[n]!='\0';n++)
	{
		//printf("now:%c, source[%d] = %c\n", item[0],n,source[n]);
		if(item[0] ==source[n])
		{
			counter = 1;
			break;
		}
	}
	if(!counter)	return -1;

	for(i = 0; source[n]!='\0'&&item[i]!='\0';n++)
	{
		if(item[i] !=source[n])
		{
			DIFFERENTcounter++;
			if(DIFFERENTcounter > SEARCH_THRESHOLD)	{	break;	}
		}else
		{
			i++;
			counter++;
		}

#ifdef DEBUG
		printf("\033[33m\tnow:%c\t",item[i]);
		printf("\tto:%c\t",source[n]);
		printf("\tcounter = %d\t", counter);
		printf("\tn  = %d\n\033[37m", n);
#endif

	}

	if(counter - strlen(item) <= SEARCH_THRESHOLD)
	{
		if(DIFFERENTcounter == 0)
		{
			//printf("Completely matched\n");
			return 0;
		}else
		{
			//printf("Incomplete matched\n");
			return 1;
		}
	}else
	{
		//printf("Unmatched\n");
		return -1;
	}
}
#endif


#if 0
//初始化数据

int InitData(char **source,char **target,int **value)
{
    char ch;
    int i = 0;

    (*source) = (char *)malloc(sizeof(char) *compare_strings_by_kmpP_MAX_SIZE);
    (*target) = (char *)malloc(sizeof(char) *compare_strings_by_kmpP_MAX_SIZE);
    (*value) = (int *)malloc(sizeof(int) *compare_strings_by_kmpP_MAX_SIZE);

    if(!(*source) || !(*target) || !(*value))return DIFFERENT;

    printf("请输入要输入源字符串,以#结束:\n");

    while((ch = getchar())!='#'){

        (*source)[i++] = ch;
        (*source)[i] = '\0';
    }
    getchar();  //抵消缓冲

    i = 0;  //重置
    printf("请输入要匹配的字符串,以#结束:\n");

    while((ch = getchar())!='#'){
        (*target)[i++] = ch;
        (*target)[i] = '\0';
    }

    //初始化value数组
    for(i = 0; i < compare_strings_by_kmpP_MAX_SIZE ;i++){
        (*value)[i] = 0;
    }
    return TWINS;
}
#endif 
